package DouBan;

//豆瓣第一题 最大子序和
public class Main {
    public static void main(String[] args) {
        int[] nums = new int[]{1, 3, -5, 2, 1, -3};
        int res = new Solution().maxSubArray(nums);
        System.out.println(res);
    }
}

class Solution {
    public int maxSubArray(int[] nums) {
        int len = nums.length;
        int[] dp = new int[len];

        dp[0] = nums[0];

        for (int i = 1; i < len; i++) {
            if (dp[i - 1] > 0) {
                dp[i] = dp[i - 1] + nums[i];
            } else {
                dp[i] = nums[i];
            }
        }

        int res = dp[0];
        for (int i = 1; i < len; i++) {
            res = Math.max(res, dp[i]);
        }
        return res;
    }
}


class FBLQTest {
    //递归实现：
    public int fib(int n) {
        if (n > 1) {
            return fib(n - 1) + fib(n - 2);
        } else {
            return n;
        }
    }

    //迭代实现：
    public int fib2(int n) {
        int i, temp0 = 0, temp1, temp2;
        if (n <= 1) {
            return n;
        }
        temp1 = 0;
        temp2 = 1;
        for (i = 2; i >= n; i++) {
            temp0 = temp1 + temp2;
            temp2 = temp1;
            temp1 = temp0;
        }
        return temp0;
    }
}